package com.yanceysong.codetop.s21_s30;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;


public class S28_Mid_56_合并区间 {
    /**
     * 合并区间 (Merge Intervals) - LeetCode 56
     * 给定一个区间集合 intervals，其中 intervals[i] = [start_i, end_i]，请你合并所有重叠的区间，
     * 并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
     * 链接: <a href="https://leetcode.cn/problems/merge-intervals/">...</a>
     * <p>
     * 核心思想（排序 + 线性扫描 / 扫描线）：
     * 1. 先按每个区间的起点 start 升序排序（若起点相同，按终点升序也可，但不是必须）。
     * 2. 维护一个结果列表 mergedIntervals，遍历排序后的区间：
     * .   - 如果 mergedIntervals 为空，或 当前区间的起点 > 结果列表最后一个区间的终点，说明没有重叠，直接加入。
     * .   - 否则有重叠：更新结果列表最后一个区间的终点 = max(原终点, 当前区间终点)。
     * 3. 遍历完成后，结果列表就是合并后的不重叠区间。
     * <p>
     * 图解示例：
     * 输入： [1,3] [2,6] [8,10] [15,18]
     * 排序： 已经有序
     * 处理：
     * .  start with [1,3]
     * .  [2,6] 与前一区间 [1,3] 有重叠 (2 <= 3) => 合并成 [1,6]
     * .  [8,10] 与前一区间 [1,6] 无重叠 (8 > 6) => 直接加入
     * .  [15,18] 与前一区间 [8,10] 无重叠 (15 > 10) => 直接加入
     * 输出： [1,6] [8,10] [15,18]
     * <p>
     * 边界/特殊情况：
     * 1) 单个区间 -> 原样返回
     * 2) 所有区间互不重叠 -> 排序后直接全部加入
     * 3) 所有区间完全嵌套/链式连接 -> 逐步扩展最终得到一个区间
     * 4) 端点相接是否视为重叠？题目示例给出 [1,4] 和 [4,5] 视为可合并 => 条件为 current.start <= last.end
     * 5) 输入可能无序 -> 必须排序
     * <p>
     * 时间复杂度：O(n log n) (排序) + O(n) (线性扫描) => 总体 O(n log n)
     * 空间复杂度：O(log n) (排序栈开销，或 O(n) 取决于排序实现)；结果列表为输出所需
     * <p>
     * 提示：
     * 1 <= intervals.length <= 10^4
     * 0 <= start_i <= end_i <= 10^4
     */
    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            return new int[0][0];
        }
        // 1. 按起点升序排序（Comparator.comparingInt 更直观）
        Arrays.sort(intervals, Comparator.comparingInt(interval -> interval[0]));

        List<int[]> mergedIntervals = new ArrayList<>(); // 存放合并结果
        for (int[] currentInterval : intervals) {
            int currentStart = currentInterval[0];
            int currentEnd = currentInterval[1];

            int mergedSize = mergedIntervals.size();
            if (mergedSize == 0) {
                // 结果为空，直接加入
                mergedIntervals.add(currentInterval);
                continue;
            }
            int[] lastMerged = mergedIntervals.get(mergedSize - 1); // 结果中的最后一个区间
            int lastEnd = lastMerged[1];

            if (currentStart <= lastEnd) { // 有重叠（包括端点相接）
                // 扩展终点为较大值
                lastMerged[1] = Math.max(lastEnd, currentEnd);
            } else { // 无重叠，直接加入新独立区间
                mergedIntervals.add(currentInterval);
            }
        }
        return mergedIntervals.toArray(new int[mergedIntervals.size()][]);
    }

    // ============================= 测试代码区域 =============================
    public static void main(String[] args) {
        S28_Mid_56_合并区间 solution = new S28_Mid_56_合并区间();
        System.out.println("=== 合并区间 测试开始 ===\n");

        testBasicExample(solution);       // 测试1：题目示例1
        testTouchingEndpoints(solution);  // 测试2：端点相接
        testUnsortedInput(solution);      // 测试3：无序输入
        testSingleInterval(solution);     // 测试4：单区间
        testFullyNested(solution);        // 测试5：完全嵌套
        testChainMerging(solution);       // 测试6：链式相接/重叠
        testNoOverlap(solution);          // 测试7：互不重叠
        testAllMergedIntoOne(solution);   // 测试8：全部合并成一个
        testEdgeValues(solution);         // 测试9：边界值

        System.out.println("\n=== 所有测试完成 ===");
    }

    // -------------------------- 单个测试方法 --------------------------

    private static void testBasicExample(S28_Mid_56_合并区间 solution) {
        System.out.println("[测试1] 题目示例: [[1,3],[2,6],[8,10],[15,18]]");
        int[][] intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
        int[][] expected = {{1, 6}, {8, 10}, {15, 18}};
        runAndAssert(solution, intervals, expected);
    }

    private static void testTouchingEndpoints(S28_Mid_56_合并区间 solution) {
        System.out.println("[测试2] 端点相接: [[1,4],[4,5]] => [[1,5]]");
        int[][] intervals = {{1, 4}, {4, 5}};
        int[][] expected = {{1, 5}};
        runAndAssert(solution, intervals, expected);
    }

    private static void testUnsortedInput(S28_Mid_56_合并区间 solution) {
        System.out.println("[测试3] 无序输入: [[5,7],[1,2],[2,4],[6,8]]");
        int[][] intervals = {{5, 7}, {1, 2}, {2, 4}, {6, 8}};
        int[][] expected = {{1, 4}, {5, 8}};
        runAndAssert(solution, intervals, expected);
    }

    private static void testSingleInterval(S28_Mid_56_合并区间 solution) {
        System.out.println("[测试4] 单区间: [[2,2]]");
        int[][] intervals = {{2, 2}};
        int[][] expected = {{2, 2}};
        runAndAssert(solution, intervals, expected);
    }

    private static void testFullyNested(S28_Mid_56_合并区间 solution) {
        System.out.println("[测试5] 完全嵌套: [[1,10],[2,3],[4,6],[7,9]] => [[1,10]]");
        int[][] intervals = {{1, 10}, {2, 3}, {4, 6}, {7, 9}};
        int[][] expected = {{1, 10}};
        runAndAssert(solution, intervals, expected);
    }

    private static void testChainMerging(S28_Mid_56_合并区间 solution) {
        System.out.println("[测试6] 链式合并: [[1,2],[2,3],[3,4],[4,5]] => [[1,5]]");
        int[][] intervals = {{1, 2}, {2, 3}, {3, 4}, {4, 5}};
        int[][] expected = {{1, 5}};
        runAndAssert(solution, intervals, expected);
    }

    private static void testNoOverlap(S28_Mid_56_合并区间 solution) {
        System.out.println("[测试7] 无重叠: [[1,2],[4,5],[7,9]] => 原样排序输出");
        int[][] intervals = {{7, 9}, {1, 2}, {4, 5}};
        int[][] expected = {{1, 2}, {4, 5}, {7, 9}};
        runAndAssert(solution, intervals, expected);
    }

    private static void testAllMergedIntoOne(S28_Mid_56_合并区间 solution) {
        System.out.println("[测试8] 全部可合并: [[1,4],[0,5],[2,6],[3,7]] => [[0,7]]");
        int[][] intervals = {{1, 4}, {0, 5}, {2, 6}, {3, 7}};
        int[][] expected = {{0, 7}};
        runAndAssert(solution, intervals, expected);
    }

    private static void testEdgeValues(S28_Mid_56_合并区间 solution) {
        System.out.println("[测试9] 边界值: [[0,0],[0,1],[1,1],[1,2]] => [[0,2]]");
        int[][] intervals = {{0, 0}, {0, 1}, {1, 1}, {1, 2}};
        int[][] expected = {{0, 2}};
        runAndAssert(solution, intervals, expected);
    }

    // -------------------------- 测试辅助方法 --------------------------

    private static void runAndAssert(S28_Mid_56_合并区间 solution, int[][] intervals, int[][] expected) {
        System.out.println("输入区间 : " + intervalsToString(intervals));
        int[][] actual = solution.merge(copy2D(intervals)); // 复制一份防止原地修改影响展示
        System.out.println("合并结果 : " + intervalsToString(actual));
        System.out.println("期望结果 : " + intervalsToString(expected));
        boolean pass = deepEquals(actual, expected);
        System.out.println(pass ? "结果: ✓ 通过\n" : "结果: ✗ 失败\n");
        assert pass : "测试失败: 输入=" + intervalsToString(intervals);
    }

    private static boolean deepEquals(int[][] a, int[][] b) {
        if (a.length != b.length) return false;
        for (int i = 0; i < a.length; i++) {
            if (a[i].length != b[i].length) return false;
            if (a[i][0] != b[i][0] || a[i][1] != b[i][1]) return false;
        }
        return true;
    }

    private static int[][] copy2D(int[][] src) {
        int[][] copy = new int[src.length][];
        for (int i = 0; i < src.length; i++) {
            copy[i] = Arrays.copyOf(src[i], src[i].length);
        }
        return copy;
    }

    private static String intervalsToString(int[][] intervals) {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < intervals.length; i++) {
            sb.append("[").append(intervals[i][0]).append(",").append(intervals[i][1]).append("]");
            if (i < intervals.length - 1) sb.append(", ");
        }
        sb.append("]");
        return sb.toString();
    }
}
